The present invention relates to a method and apparatus for global routing performed prior to detailed routing in computer-aided automatic layout design of LSI and VLSI and a storage medium, readable by a computer, having a global routing program stored therein, and particularly, to a method and apparatus for global routing used in order to search the minimum cost routing between net terminals using a Steiner tree and a storage medium, readable by a computer, having a global routing program stored therein.
In a CAD system used for automatically designing a large scale semiconductor integrated circuit such as LSI and VLSI using a computer, firstly, a logical design is performed that determines cells such as AND and OR therebetween and nets connecting the cells therebetween; secondly, an automatic design for cell layout placing the cells on a chip is performed based on a netlist obtained by the logical design and finally, routing is performed that determines wires connecting nets between the cells placed on the chip. The routing is divided into two phases: one is global routing in which net routing is determined without considering timing, delay and so on and the other is detailed routing in which actual routing on the chip is determined in consideration of timing, delay and others. Along with progress in circuit design technology in recent years, improvement on degree of integration in VLSI and increase in circuit scale have been tremendous. For this reason, automatic layout design faces requirement for high speed processing of a large scale circuit.
Simple description will be given, here, of a definition of a global routing problem, an object of the present invention. Consider a region on a grid structure called a grid graph. A grid graph is obtained by a procedure in which a chip region is divided into cell blocks with horizontal and vertical lines and thus formed rectangular cells are represented by vertices and the vertices are connected to form a grid structure, and a terminal of a layout cell is expressed by a black point on a grid structure. Intersections of the horizontal and vertical lines of the grid graph are called grids. A grid size is a total number of grids and in a case where the number of grids in the vertical direction is v counts and the number of grids in the horizontal direction is h counts, the grid size is a value of (hxc3x97v). In a case of FIG. 1, h=6 and v=6, so a grid size is 36. A global routing problem is to generate line segments on a grid structure so as to connect terminals t1, t2 ad t3 of a net N therebetween with the line segments. In a case where a plurality of wiring layers exist, each line segment is allotted on a route of the lowest cost. A cost function is generally a wirelength given by a total sum of lengths of line segments and the cost is minimized. Constraints on global routing is not to pass through regions 100 and 102 shadowed with hatching, which regions are a wiring prohibiting region or a highly wiring congested region.
Concise description will be given of well known ones of global routing methods below:
Typically, a maze method and a line search method are named as first two which are procedures regarding a net with two terminals. The maze method is effected as follows: As shown in FIG. 2, one terminal t1 is a source and the other terminal t2 is a target, and search is performed in a way such that a wave is propagated from the source t1. At first, the source t1 is labeled with [0]. A value of the label is a distance from the source t1. Then, a vertex adjacent to the source t1 is labeled with [1] and a vertex adjacent to the vertex of label [1] is labeled with [2]. Such a procedure is advanced such that a wave propagates. The process is repeated till the wave reaches the target t2 or till the wave is not propagate any longer. A strong point of the maze method is that the shortest route can be obtained even in consideration of a region where no wiring can be effected. Furthermore, a calculation time is dependent on a grid size, which is O(hxc3x97w) wherein a height is indicated by h and a width by w, and O( ) is Order( ) for short. For this reason, the a maze method increases a calculation cost with increase in scale of a circuit and therefore, increase in grid size. Moreover, a memory size for use in storing labels is also dependent on a grid size of a chip.
A line search method is such that as in FIG. 3, line segments are generated from the source t1 and the target t2 and the line segments are added into lists called an s list and a t list, respectively. A line segment is elongated as long as no obstacle is encountered by the line segment. Search is terminated where a line segment of the s list and a line segment of the t list are encountered by each other. In FIG. 3, line segments are elongated such that line segments s1, s2 and s3 are added to the s list and line segments s4, s5 and s6 are added to the t list and such a process is terminated where the line segments s2 and s4 are encountered by each other to find a route. The line search method reduces the use of a memory by employing line segments instead of grids. In this method, a calculation cost is dependent on the number of line segments L, which is O(L). Such maze and line search methods are capable of not only considering regions 100 and 102, which regions are a wiring prohibiting region or a highly wiring congested region as obstacles, but performing a multilayer wiring.
Extended methods of the maze method and the line search method are employed for a multiterminal net with three or more terminals, but such an extended method has a defect of falling into a local solution; therefore, a method using a Steiner tree of FIG. 4 is more excellent in that a high quality solution is obtained. The method using a Steiner tree generates a Sterner tree 104 called RST (rectilinear Steiner tree). A problem of searching the Steiner tree 104 with the minimum cost cannot be solved in a significant time and is of a non-polynominal order complexity that solutions increases in an explosive manner or of no solution being obtainable in polynominal time, but some heuristic methods have been proposed for the problem. A proposed method known is such that when the number of nets is N by definition, the method requires a calculation time and a used memory amount up to the order of O(N3logN). A general method using a Steiner tree is performed such that a Steiner tree is generated without any of constraints and in no consideration of obstacles, and when routes of branches of the Steiner tree are obtained, the obstacles are avoided using a maze method or the like.
In a method dependent on a grid size such as a maze method, a problem arises since a calculation time and a used memory amount are increased in a large scaled circuit. On the other hand, the method using Steiner tree has dependency of a calculation time on the number of net terminals. The number of net terminals is at the most several hundreds in a practical circuit. In contrast to this, a grid size of a wiring region amounts to at least several millions or more. Therefore, the method using a Steiner tree is more advantageous in calculation time and used memory amount compared with the maze method. In a general algorithm for generating a Steiner tree, however, no consideration is given to layers, prohibition, a wiring capacity; therefore, such constraints are left up to detailed routing. In this case, a problem imposed on the detailed routing becomes hard and contrary to the expectation, a possibility arises of increasing a calculation time for all the wiring.
According to the present invention, provided are a method and apparatus for global routing capable of obtaining a high quality solution for global routing that alleviates a load on detailed routing using a Steiner tree, and a storage medium, readable by a computer, having a global routing program stored therein.
The present invention is a global routing method obtaining global routing between net terminals of cells placed on a chip and the method includes: a Steiner tree generating step of generating a Steiner tree having been generated without any of constraints as an initial solution: and a correcting step of repeating partial correction of the Steiner tree so as not to increase a line length as far as possible in consideration of constraints based on the initial solution of the Steiner tree to obtain the global routing, wherein in the Steiner tree generating step, a Steiner tree is generated, as an initial solution, without any of constraints such as layers, prohibition and a wiring capacity and in the correcting step, partial correction of the Steiner tree is repeated so as not to increase a line length as far as possible in consideration of a prohibiting region, a wiring capacity and layers. The present invention can achieve a result of the same quality as global routing by means of a maze method in consideration of an obstacle by performing a partial correction of a Steiner tree while taking constraints on wiring into consideration. Furthermore, calculation required for partial correction of a Steiner tree in the present invention is fundamentally coordinate computation, and a calculation time and a used memory amount are dependent on the number N of net terminals. Therefore, in a large scale circuit, the method of the present invention is more advantageous in calculation time and used memory amount compared with a maze method scanning a wiring region. Herein, the correcting step includes: a path collection generating step of generating a path collection obtained by dividing the Steiner tree into a plurality of paths each having at least a Steiner point, as a value, being an intersection of 3 or more branches; and a path correcting step of partially correcting the Steiner tree by correction of a path in consideration of constraints for the path collection of the Steiner tree. In this path collection, when the number of terminals is N, and the number of Steiner points is an (N) order, the number of branches of the Steiner tree is en by definition, a calculation time for division to paths is of the order of O(en2) since the time is suppressed by an operation for determining whether or not each terminal point of a branch is a Steiner point. Moreover, the number en of branches of the Steiner tree is of the order of O(N) and a calculation time for division to paths is of O(N2). Furthermore, the number of paths generated is suppressed to O(N). The path correcting step includes a prohibiting region rerouting step of changing a path passing through a prohibiting region to a path not passing through the prohibiting region for a path collection of a Steiner tree. The prohibiting region rerouting step has the following steps, to be concrete:
I. determining whether a start point or end point of a path resides in or a route thereof passes through a prohibiting region;
II. if neither reside in nor passing through the prohibiting region, then terminating the process;
III. if the start point or end point or the path resides in the prohibiting region, then moving the start point or end point to outside the prohibiting region and thereafter, renewing a path collection, or if neither being found outside the prohibiting region, then changing no path and terminating the process; and
IV. if a path passes through a prohibiting region, then changing a route thereof so as not pass through the prohibiting region.
The prohibiting region rerouting step includes: a first correcting step and a second correcting step. In the first correcting step, when a start point in a prohibiting region is moved to outside the region, points on branches of a Steiner tree traceable from an original start point is selected as prospective points for a new start point of a movement destination or points on all branches of the Steiner tree traceable from an original end point is selected as prospective points for a new end point of a movement destination, and a prospective point, being outside the prohibiting region, and having the shortest line length is selected among the prospected points as a start point or endpoint to change a path. In this case, a calculation time for correcting one path is of O(en)=O(N). In the second correcting step, when a route passes through a prohibiting region, a path is changed selecting a route passing through a space outside the prohibiting region without changing both of the start and end points so as not to increase a line length as far as possible. In order not to increase a line length of a path compared with the original Steiner tree in the second correcting step, it is only required to select a route passing through a rectangle encircling the start and end point of the path. In a case where it is impossible for a path to pass through a space within the rectangle due to a constraint from the prohibiting region, a line length increases. Moreover, by predetermining routing patterns within a rectangle, a calculation time can be limited to O(1). The path correcting step includes a wiring congested region rerouting step of changing a path passing through a wiring congested region having the number of wires exceeding a wiring capacity to a path not passing through the wiring congested region so as to ensure the number of wires equal to or less than the wiring capacity in the wiring congested region. The wiring congested region rerouting step has a detailed procedure including the steps of:
I. defining a wiring capacity indicating the maximum of the number of wires capable of passing through each of blocks obtained by dividing a wiring region into the blocks each of a prescribed area and a wiring congestion level indicating the number of wires currently passing through each of the blocks;
II. if a wiring congestion level of a block is equal to or less than a wiring capacity thereof, then terminating the process;
III. if a wiring congestion level of a block exceeds a wiring capacity thereof, then changing a first path whose start point and end point are outside a block, and passing through the block to a second path finding a route not passing through the block without changing a start point and end point of the first path, or if no route not passing through the block is found, maintaining the first path as is originally;
IV. if one of a start point and endpoint of a path resides within a block and the other resides outside the block, changing the path finding a terminal point outside said block instead of a terminal point within said block and thereby finding a route not passing through the lock, or if neither the terminal point nor the route is found, maintaining the path as is originally;
V. if both of a start point and end point of a path resides in a block, maintaining the path as is originally; and
VI. after a path is corrected, recalculating a wiring congestion level of a block and repeating the process till the wiring congestion level thereof decreases to a value equal to or less than a wiring capacity thereof.
This wiring congested region rerouting step can also include: a first correcting step and a second correcting step. In the first correcting step, when a start point or end point of a path resides in a wiring congested block, points on branches of a Steiner tree traceable from an original start point or end point are selected as prospect points for a new start point or new end point of a movement destination, and a path is changed selecting a prospect point, being outside the block, and having the shortest line length among the prospective points for the new end point or end point to find a route not to passing through the block. In the second correcting step, when a route passes through a block, a path is changed selecting a route passing through a space outside the block so as not to increase a line length as far as possible without changing a start point and end point thereof. The path correcting step includes a line length improving step of changing a path so as to improve a line length of the path after partial correction of a Steiner tree under constrains for a path collection of the Steiner tree. The line length improving step has a detailed procedure including the steps of:
I. removing branches belonging to a path to be processed from a Steiner tree to divide the branches into a first tree fraction T1 which is a collection of branches traceable from a start point and a second tree fraction T2 which is a collection of branches traceable from an end point;
II. generating a first prospective path finding an end point on a branch, having the shortest Manhattan distance, among branches of the tree fraction T2 from the original start point of the first tree fraction T1;
III. generating a second prospective path finding a start point on a branch, having the shortest Manhattan distance, among branches of the tree fraction T1 from the original end point of the second tree fraction T2;
IV. if a distance d1 of the first prospective path is equal to or less than a distance d2 of the second prospective path and equal to or less than a distance d of the pass to be processed, that is, if d1 less than d2 and d1 less than d, renewing a path collection with the first prospective path whose end point has been changed as a new path;
V. if a distance d2 of the second prospective path is equal to or less than a distance d1 of the first prospective path and equal to or less than a distance d of the pass to be processed, that is, if d2 less than d1 and d2 less than d, renewing the collection path with the second prospective path whose end point has been changed as a new path; and
VI. If distances d1 and d2 of the first and second prospective paths, respectively, are equal to or more than a distance of the path to be processed, that is if d1xe2x89xa7d and d2xe2x89xa7d, maintaining the path as is originally without changing a start point and end point thereof.
Furthermore, the present invention provides a global routing apparatus acquiring global routing between net terminals of cells placed on a chip. The global routing apparatus includes: a Steiner tree generating unit generating a Steiner tree having been generated without any of constraints such as layers, prohibition and a wiring capacity as an initial solution; a path collection generating unit generating a path collection obtained by dividing the Steiner tree into a plurality of paths each having at least a Steiner point, as a value, being an intersection of three or more branches; and a path correcting unit obtaining global routing repeating partial correction of the Steiner tree with correction of a path in consideration of the constraints so as not to increase a line length as far as possible for the path collection of the Steiner tree. The path correcting unit of the global routing apparatus includes: a prohibiting region rerouting processing unit changing a path passing through a prohibiting region to a path not passing through the prohibiting region for a path collection of the Steiner tree; a wiring congested region rerouting processing unit changing a path passing through a wiring congested region having the number of wires exceeding a wiring capacity to a path not passing through the wiring congested region so as to ensure the number of wires equal to or less than the wiring capacity in the wiring congested region for the path collection of the Steiner tree; and a line length improvement processing unit changing a path so as to improve a line length of the path after partial correction of said Steiner tree under the constraints for the path collection of the Steiner tree.
Furthermore, the present invention provides a storage medium, readable by a computer, having a global routing program stored therein, the program acquiring global routing between net terminals of cells placed on a chip. The storage medium includes: a Steiner tree generating module generating a Steiner tree having been generated without any of constraints such as layers, prohibition and a wiring capacity as an initial solution; a path collection generating module generating a path collection obtained by dividing the Steiner tree into a plurality of paths each having at least a Steiner point, as a value, being an intersection of three or more branches; and a path correcting module obtaining global routing repeating partial correction of the Steiner tree with correction of a path in consideration of constraints so as not to increase a line length as far as possible for a path collection of the Steiner tree. Furthermore, the path correcting module of the storage medium includes: a prohibiting region rerouting processing module changing a path passing through a prohibiting region to a path not passing through the prohibiting region for a path collection of a Steiner tree; a wiring congested region rerouting processing module changing a path passing through a wiring congested region having the number of wires exceeding a wiring capacity to a path not passing through the wiring congested region so as to ensure the number of wires equal to or less than the wiring capacity in the wire congested region for the path collection of the Steiner tree; and a line length improvement processing module changing a path so as to improve a line length of the path after partial correction of a Steiner tree under the constraints for the path collection of the Steiner tree.
A calculation time for correction of a Steiner tree in such a global routing method of the present invention is only of the order of O{N2(logN)2} for a net with the number N of terminals. Besides, a calculation time of a combination of generation and correction of a Steiner tree as an initial solution is of the order of O(N3logN) though the time is dependent on a Steiner generating algorithm. The number of terminals is at the most 102 and while in this case, a calculation time is 108, a net having several hundreds of terminals is only several % of all the nets in a general circuit. Moreover, a necessary memory capacity for preparing a path structure is O(N). On the other hand, a grid size is of the order ranging from 106 to 108. In a maze method, a calculation time for a grid size of (hxc3x97w) is O(hxc3x97w) and the calculation is repeated in times equal to the number of nets. Moreover, a memory is required for storing label values corresponding to a grid size. As a result, according to the present invention, realized is global routing with a short calculation time and a small used-memory amount.